#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
题目描述
有一只乌龟，初始在0的位置向右跑。
这只乌龟会依次接到一串指令，指令T表示向后转，指令F表示向前移动一个单位。乌龟不能忽视任何指令。
现在我们要修改其中正好n个指令（一个指令可以被改多次，一次修改定义为把某一个T变成F或把某一个F变成T）。
求这只乌龟在结束的时候离起点的最远距离。（假设乌龟最后的位置为x，我们想要abs(x)最大，输出最大的abs(x)）
输入描述:
第一行一个字符串c表示指令串。c只由F和T构成。
第二行一个整数n。
1 <= |c| <= 100, 1 <= n <= 50
输出描述:
一个数字表示答案。
示例1

https://www.cnblogs.com/shoulinniao/p/10584699.html
"""


class TurtleRun:
    POS = 1
    NEG = -1

    def __init__(self, instructions_str, modify_times):
        self.ins = instructions_str
        self.len = len(instructions_str)
        self.times = modify_times

        self.memory = set()

        self.dis = 0
        self.max_rec(0, self.times, self.POS, 0)

        # print(self.dis)

    def max_rec(self, cur_idx, remain_times, direction, distance):
        if cur_idx == self.len:
            if remain_times%2 == 0:
                # self.min = min( abs(distance), self.min )
                self.dis = max( abs(distance), self.dis )
            return

        key = (cur_idx, remain_times, direction, distance)
        if key in self.memory:
            # print('hit', key)
            return
        self.memory.add(key)

        # 1: Do not change cur instruction
        if self.ins[cur_idx] == 'T':
            self.max_rec(cur_idx+1, remain_times, -direction, distance)
        else:
            self.max_rec(cur_idx+1, remain_times, direction, distance + direction)

        # 2: Change cur instruction
        if remain_times:
            if self.ins[cur_idx] == 'T':
                self.max_rec(cur_idx+1, remain_times-1, direction, distance + direction)
            else:
                self.max_rec(cur_idx+1, remain_times-1, -direction, distance)


def test():
    t = TurtleRun("FFF", 2)
    assert t.dis == 3

    t = TurtleRun("FFF", 1)
    assert t.dis == 2

    t = TurtleRun("FT", 1)
    assert t.dis == 2

    t = TurtleRun("TFFTFTFTFFTT", 1)
    assert t.dis == 5

    t = TurtleRun("FFFTFFF", 2)
    assert t.dis == 6


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
